#define _CRT_SECURE_NO_WARNINGS 1
#include "heap2.h"

//堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);

	hp->data = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

//堆的销毁
void HeapDestroy(Heap* hp)
{
	assert(hp);

	free(hp->data);
	hp->data = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

//交换
void Swap(HeapDataType* a1, HeapDataType* a2)
{
	HeapDataType tmp = *a1;
	*a1 = *a2;
	*a2 = tmp;
}

//向上调整
void AdjustUp(HeapDataType* a, int child)
{
	assert(a);

	//计算出第一次父亲节点的下标
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//小堆，如果child小于parent就交换
		//大堆，如果child大于parent就交换
		if (a[child] < a[parent])//此时为小堆
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//堆的插入
void HeapPush(Heap* hp, HeapDataType x)
{
	assert(hp);

	//判断是否需要扩容
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
		HeapDataType* new = (HeapDataType*)realloc(hp->data,sizeof(HeapDataType) * newcapacity);
		if (new == NULL)
		{
			perror("realloc");
			return;
		}
		hp->data = new;
		hp->capacity = newcapacity;
	}

	//插入
	//size指向的是最后一个数据的下一个位置
	hp->data[hp->size++] = x;

	//向上调整
	//hp->size-1指的是插入节点的下标
	AdjustUp(hp->data, hp->size - 1);
}

//向下调整算法
void AdjustDown(HeapDataType* a, int parent, int size)
{
	assert(a);

	//小堆，与左右孩子中较小的交换
	//大堆，与左右孩子中较大的交换
	//假设法
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (a[child] > a[child + 1] && child + 1 < size)//此时为小堆
		{
			child += 1;
		}
		if (a[parent] > a[child])//此时为小堆
		{
			//交换
			Swap(&(a[parent]), &(a[child]));
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);//堆不能为空

	//交换堆顶数据和最后一个叶子的数据
	Swap(&(hp->data[0]), &(hp->data[hp->size - 1]));

	//删除最后一个叶子节点
	hp->size--;

	//使用向下调整算法，使之依旧为堆
	AdjustDown(hp->data,0,hp->size);//参数分别为：存放数据的数据、从哪个位置开始向下调整、数据的个数
}

//取堆顶的数据
HeapDataType GetHeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	return hp->data[0];
}

//判空
int HeapEmpty(Heap* hp)
{
	assert(hp);

	if (hp->size == 0)
	{
		return 1;
	}
	else
	{
		return -1;
	}
}

//获取堆的数据个数
int GetHeapSize(Heap* hp)
{
	assert(hp);
	
	return hp->size;
}